package com.blink.optimize.algorithm.lfu;

import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.concurrent.atomic.AtomicInteger;

/**
 * <Description>Least Frequently Used </Description>
 * <ClassName> LFUCache</ClassName>
 *
 * @Author liuxianzhao
 * @Date 2018年01月09日 11:10
 */
public class LFUCache {
    private int cacheMaxSize;
    private Object[] cacheData;
    private Map<String, Integer> cacheDataIndex;
    private Map<String, AtomicInteger> cacheUserCount;

    public Object get(String key) {
        if (key == null) {
            throw new IllegalArgumentException("key can not be null");
        }
        Integer index = cacheDataIndex.get(key);
        if (null == index) {
            return null;
        }
        cacheUserCount.get(key).incrementAndGet();
        return cacheData[index];
    }

    public synchronized Object put(String key, Object o) {
        if (key == null) {
            throw new IllegalArgumentException("key can not be null");
        }
        if (null != cacheDataIndex.get(key)) {
            cacheData[cacheDataIndex.get(key)] = o;
            return o;
        }
        int position = 0;
        if (cacheDataIndex.size() == cacheMaxSize) {
            position = release();
        } else {
            position = cacheDataIndex.size();
        }
        cacheData[position] = o;
        cacheDataIndex.put(key, position);
        cacheUserCount.put(key, new AtomicInteger(0));
        return o;
    }

    private int release() {
        int min = -1;
        String minKey = null;
        int count = 1;
        for (Map.Entry<String, AtomicInteger> s : cacheUserCount.entrySet()) {
            if (count > 1) {
                if (s.getValue().get() < min) {
                    min = s.getValue().get();
                    minKey = s.getKey();
                }
            } else {
                min = s.getValue().get();
                minKey = s.getKey();
            }
            count++;
        }
        Integer integer = cacheDataIndex.get(minKey);
        cacheDataIndex.remove(minKey);
        cacheUserCount.remove(minKey);
        return integer;
    }

    public static LFUCache create(int cacheMaxSize) {
        return new LFUCache(cacheMaxSize);
    }

    private LFUCache(int cacheMaxSize) {
        this.cacheMaxSize = cacheMaxSize;
        cacheData = new Object[cacheMaxSize];
        cacheDataIndex = new HashMap<>();
        cacheUserCount = new LinkedHashMap<>();
    }

    public int getCacheMaxSize() {
        return cacheMaxSize;
    }

    public Object[] getCacheData() {
        return cacheData;
    }
}
